/*
线性表：n个相同数据类型的数据元素的有限序列。(数据类型可以是结构体)
    
    顺序表： 逻辑上相邻的元素，物理存储空间也连续。

    链表： 逻辑上相邻的元素，物理存储空间不一定连续。
*/

#include<stdio.h>
#include<string.h>

/*
typedef struct 
{
    int book_id;
    char book_name[20];
    double book_price;
}book;

int main()
{
    book b;
    b.book_id = 10086;
    strcpy(b.book_name, "C语言");
    b.book_price = 99.9;
    printf("书号：%d\n书名：%s\n价格：%.2f\n", b.book_id, b.book_name, b.book_price);
}
*/

//顺序表

#define MAXSIZE 100
typedef int ElemType;

//创建顺序表结构体
typedef struct 
{
    ElemType data[MAXSIZE];
    int length;
}SeqList;

//初始化顺序表
void InitList(SeqList *L) //初始化顺序表，传入顺序表指针（地址）
{
    L->length = 0; //length默认没有赋值，初始化为0
}

//在尾部添加元素
void AddList(SeqList *L, ElemType e)
{
    if (L->length >= MAXSIZE)
    {
        printf("顺序表已满\n");
        return;
    }
    L->data[L->length] = e;
    L->length++;
}

//插入元素
void InsertList(SeqList *L, int i, ElemType e)
{
    if (i < 1 || i > L->length + 1)
    {
        printf("插入位置错误\n");
        return;
    }
    
    if (L->length >= MAXSIZE)
    {
        printf("顺序表已满\n");
        return;
    }

    for (int j = L->length; j >= i;j--)
    {
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
    printf("插入成功\n");

}

//删除元素（后面的把前面的覆盖）
void DeleteList(SeqList *L, int i, ElemType *e)
{
    if(L->length == 0)
    {
        printf("顺序表为空\n");
        return;
    }
    if (i < 1 || i > L->length)
    {
        printf("删除位置错误\n");
        return;
    }

    *e = L->data[i-1];//存放被删除的数据
    for (int j = i; j < L->length; j++) //实际上最后一个位置的元素没有往前挪，不用管，因为最后会length--，下次添加的时候会覆盖
    {
        L->data[j-1] = L->data[j];
    }
    L->length--;
    printf("删除成功\n");

}

//查找数据位置
int LocateElem(SeqList *L, ElemType e)
{
    for (int i = 0; i < L->length; i++)
    {
        if (L->data[i] == e)
        {
            return i+1;
        }
    }
    return 0;
}

//遍历顺序表
void TraverseList(SeqList *L)
{
    for (int i = 0; i < L->length; i++)
    {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

int main()
{
    //声明并初始化list
    printf("初始化顺序表\n");
    SeqList list;
    InitList(&list);
    printf("初始化成功，目前长度占用%d\n", list.length);
    printf("目前占用内存%zu 字节\n",sizeof(list.data));
    printf("------------------------------------\n");

    //尾部添加元素
    printf("尾部添加元素\n");
    AddList(&list, 1);
    AddList(&list, 2);
    AddList(&list, 3);
    AddList(&list, 4);
    printf("------------------------------------\n");

    //遍历
    printf("遍历\n");
    TraverseList(&list);
    printf("目前长度占用%d\n", list.length);
    printf("------------------------------------\n");

    //插入元素
    printf("插入元素\n");
    InsertList(&list, 5, 5);//尾加
    TraverseList(&list);
    InsertList(&list, 1, 6);//头加
    TraverseList(&list);
    InsertList(&list, 3, 7);//中间加
    TraverseList(&list);
    printf("目前长度占用%d\n", list.length);
    InsertList(&list, 0, 8);//头溢出加
    TraverseList(&list);
    printf("目前长度占用%d\n", list.length);    
    InsertList(&list, 9, 10);//尾溢出加
    TraverseList(&list);
    printf("目前长度占用%d\n", list.length);
    InsertList(&list, 7, 9);//尾前加
    TraverseList(&list);
    printf("------------------------------------\n");

    //删除元素
    printf("删除元素\n");
    ElemType delData;
    DeleteList(&list, 5, &delData);
    printf("被删除的元素是%d\n", delData);
    TraverseList(&list);
    printf("------------------------------------\n");

    //查找数据位置
    printf("查找数据位置\n");
    ElemType findData;
    printf("请输入要查找的数据:");
    scanf("%d", &findData);
    int index = LocateElem(&list, findData);
    printf("%d的位置是%d\n", findData,index);
    printf("------------------------------------\n");

    return 0;
}
